\chapter{中间代码生成}
		\section{导入}
		\subsection{为什么要研究语义分析}
		词法分析是基于有限状态自动机，扫描识别字符串序列中的语素（关键字、标识符、运算符、常数、界符等），为下一部的语法分析做基础。
		
		语法分析是基于自底向上或自顶向下的分析方法，检查词法分析处理过后的语素集合是否能被该编程语言产生式匹配的过程，这个过程会隐式的生成语法树。在语法分析里，我们可以检查代码更大粒度的正确性。
		
		符号表被很多人认为是语义分析的一部分（剩下的一块拼图就是本章的中间代码生成）。在平时编译阶段，对于类型检查，如将整型当作数组类型使用；控制流，如C语言中大括号的使用是否前后呼应；重复定义，如不能在一个函数中重复定义两次同一个变量；作用域，如全局变量和局部变量的使用等，这些问题，通过语义分析可以找出。
		
		自然语言的语义与程序语言的语义是不一样的，严格意义上讲，自然语言的语义会非常丰富，而程序语言的语义相对固定。语义分析的目的是利用语法分析的结果，把源语言转换成机器可读的形式，称为中间代码，这个过程也称为语义分析。生成中间代码的过程，要去定义一些语义动作，这些语义动作就是语法分析每一个局部的结果，后面会有例子。
		\subsection{为什么需要生成中间代码}
		在程序编译过程中，可执行代码与具体的操作系统、硬件等相关，而生成的中间代码与操作系统、硬件设施无关，具有较好的移植性，方便了编译器系统的开发。另一方面，也便于进行优化操作，如程序中的1+2，在经过优化后直接变成3，这样的话，就节省了一步，如果是在循环或实时系统中，这样的优化就十分关键
		
		另一个原因就是直接把源语言转换成汇编指令，这种方式的好处是效率高，缺点是无法把中间过程进行分解，系统复杂，不易调试。常用手段是两小步的方法，先把源语言转换成中间代码，然后再把中间代码转换成目标语言。
		
		概括性的总结一下这一小节:
		\begin{enumerate}
			\item 易于修改，对于复杂的系统来讲，一般用模块化进行开发，把大任务或复杂问题简化，这里有一个重要的概念——耦合，我们希望模块间的耦合度不要太大，加入中间代码也是降低模块间耦合度的一种方式，使用中间代码这种特殊的表达形式来作为中间衔接，而不是程序接口这种简单复杂的形式，易于开发、调试、维护。
			\item 跨平台，易于迁移。
			\item 首先生成中间代码给了我们更多的优化算法介入的空间，因为越抽象底层的代码优化起来难度更大，先生成可转为汇编的中间语言，让我们既朝底层更进一步，却也保留了一些优化的可能性，毕竟汇编确实看起来让人觉得有些繁琐。
		\end{enumerate}
		
		\section{中间代码生成}
		\subsection{常用的中间代码形式}
		中间代码可以理解成一个源语言句子表示成机器容易理解的形式，这种形式可以很容易地转化成目标语言。
		
		设有赋值语句：$x = a * b + c$ ，则有以下中间语言：
		
		（1）逆波兰式：$xab*c+=$
		
			在编写计算器程序时，使用的就是逆波兰式的形式。以a+b为例，我们平时写的a+b这种形式，是中缀式，而逆波兰式形式得到的是ab+，又称后缀式，将操作项放在前面，运算符放在后面。
			
			
		（2） 四元式

\begin{figure}[H]
	\centering
	
	\input{./chapter7/figures/figure-Quadratic}
	\label{fig:74}
\end{figure}
四元式表示一元或二元运算，可以顺序地把程序执行的过程表达出来。第一条四元式表示，用*对a和b进行操作，结果赋给t1。第二条表示，t1与c相加，结果赋给t2。第三条表示，把t2的值赋给x。这个过程与赋值语句x = a * b + c是一样的。四元式也可以简单地写成二元运算的形式，左边和右边框表示的含义是一样的，一般写成左边这种方式，比较规整。

四元式形式具有更强的表达能力和可读性，因此在后续中间代码生成中使用更多。

（3）三元式

三元式和四元式的区别在于，四元式的最后一项叫结果变量，而三元式没有，是用\ding{172}来表示计算的结果。
\begin{center}
	\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
		\large{	\ding{172}  (*\quad a \quad b)\\
			\ding{173}  (+\quad \ding{172}\quad c)\\
			\ding{174}  (=\quad \ding{173} \quad x)}
	\end{tcolorbox}
\end{center}

（4）语义树


\begin{figure}[H]
	\centering
	\input{./chapter7/figures/figure-Semantic-tree}
	\label{fig:76}
\end{figure}
把a*b进行计算，结果在与c相加，最终把结果赋给x。

这四种方式是常用的形式，还有很多其它方式，这里不一一列举。这四种方式都是非常有效的中间代码表示形式，把程序语言表示成一种便于计算机计算的方式。这四种方式也各有优缺点，简单总结一下：
\begin{center}
	\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
		\large{	逆波兰式\textbf{简单}；四元式\textbf{清楚}；\\
			三元式\textbf{节省}；语义树\textbf{直观}；}
	\end{tcolorbox}
\end{center}


\subsection{各种语法成分的中间代码设计}
\subsubsection{逆波兰式}
给定一个表达式，可以把它写成逆波兰式的形式。逆波兰式把运算符放在操作数的后面比如：
$$
a + b \implies a b +
$$
\subsubsection{表达式的逆波兰式设计}

设pos(E)为表达式E的逆波兰式；
则：

\ding{172}$pos(E1\omega E2) = pos(E1)pos(E2)\omega$

\ding{173}$pos((E)) = pos(E)$

\ding{174}$pos(i) = i$

其中，ω是运算符，i是运算对象（变量或常量）

【注】（1）上述三个定义式，为逆波兰翻译法则；
（2）定义式中的ω为E1ωE2中最后运算的算符！例如，式a+b*c中，E1相当于a，	E2相当于b*c，ω为+。
\begin{example}
	表达式逆波兰式翻译示例
\end{example}

$x*(a+b/d)<(-e+5)$，求该表达式的逆波兰式pos()?

因为表达式中$<$的优先级最低，所以ω为$<$，E1为x*(a+b/d)，E2为(-e+5)，所以得pos(x*(a+b/d))pos((-e+5))$<$。pos(x*(a+b/d))中*最后运算，得x pos((a+b/d))*；pos((-e+5))根据式\ding{173}，得pos(-e+5)。pos((a+b/d))中+最后算，得a pos(b/d)+，pos(b/d)再得到bd/。pos(-e+5)里最后算的是+，得pos(-e)5+，在这里把-e的-定义取负，是一个单目运算，于是pos(-e)得e- 。最终得到如下所示逆波兰式。
\begin{center}
	\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
		\begin{align*}
			\because\  &pos(x*(a+b/d)<(-e+5)) \\
			&= pos(x*(a+b/d))\ pos(-e+5) <\\
			&= x\ pos((a+b/d))\ *pos(-e+5) <\\
			&=x\ a\ pos((b/d))\ +*pos(-e+5) <\\
			&=x\ a\ bd/\ +*pos(-e+5) <\\
			&=x\ a\ bd/\ +*pos(-e)5\ + <\\
			&=x\ a\ bd/\ +*e-5\ + <\\
			\therefore\ & pos()=xabd/+*e-5+<
		\end{align*}
	\end{tcolorbox}
\end{center}
\begin{center}
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=注,valign=scale,halign=center,width=\columnwidth/2]
		单目运算符的逆波兰式，$pos(-e)=e-$，请大家和双目运算符加以区分
	\end{tcolorbox}
\end{center}

\begin{example}
	其它语法成分的逆波兰式设计示例
\end{example}


\begin{definition}
	单目运算“-”的逆波兰式
	
	
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=,valign=scale,halign=center,width=\columnwidth/2]
			pos(-E)$\implies$pos(E)- 或0 pos(E) -
		\end{tcolorbox}
	\end{center}
	
	
	
\end{definition}

\begin{definition}赋值语句的逆波兰式
	
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=,valign=scale,halign=center,width=\columnwidth/2]
			v=E $\implies$ v pos(E) =
		\end{tcolorbox}
	\end{center}
	
	
\end{definition}


\begin{example}
	x=(a+b)/-e*5，pos()?
	
	首先，= 优先级最低，得x pos((a+b)/-e*5)=。pos((a+b)/-e*5)里最后操作的是*，得pos((a+b)/-e)pos(5)*。接下来的过程省略，结果如图所示
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
			\begin{align*}
				\because\  &pos(x=(a+b)/-e*5) \\
				&= x\ pos((a+b)/-e*5) =\\
				&= x\ pos((a+b)/-e)pos(5)* =\\
				&=x\ pos(a+b)pos(-e)/\ 5* =\\
				&=xab+e-/\ 5* =\\
				\therefore\ & pos()=xab+e-/\ 5* =
			\end{align*}
		\end{tcolorbox}
	\end{center}
\end{example}
	
	\subsubsection{四元式}
	逆波兰式更多是用来计算表达式，其它比如说if语句、while语句不太容易用逆波兰式，因为不是简单的代数运算。还有很多标志符没有操作数，语义很复杂，这时候编译器更常用四元式。
	
	1、表达式的四元式设计：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-design}
		
		\label{fig:81}
	\end{figure}
	四元式如q所示，包括四个部分：算符、对象1、对象2和结果，分别用ω、o1、o2和t表示。o1和o2用ω进行计算，结果存到t。
	
	设quat(E)，res(E)分别为表达式E的四元式和结果变量。
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-display}
		\label{fig:82}
	\end{figure}
	规则\ding{172}，求E1ωE2的四元式quat(E1ωE2)，先写出E1、E2的四元式quat(E1)、quat(E2)，结果分别是res(E1)、res(E2)。这两个结果经过ω计算，最终放到一个变量ti，ti就是整个表达式的结果res(E1ωE2)。
	
	【注】
	
	（1）方框内的三个定义式，为四元式翻译法则；
	
	（2）定义式中的ω为E1ωE2中最后运算的算符！
	
	
	
	
	\begin{example}表达式四元式翻译示例：
		
		a+b*(c-d)
		
		\begin{figure}[H]
			\centering
			\input{./chapter7/figures/figure-Quaternion-example}
			\label{fig:83}
		\end{figure}
		
		ω是+，E1的四元式是quat(a),E2的四元式是quat(b*(c-d))，最后一条语句是q(+ res(a) res(b*(c-d)) t)，E1的四元式是res(a),E2的四元式结果是res(b*(c-d))，把它们做加法运算，将结果存到变量t。
		
		quat(a)是空，quat(b*(c-d))需要根据准则继续求。ω是*，quat(b)是空，quat((c-d))是q(- c d t1),对于q(* res(b) res(c-d) t)，res(b)是b，res(c-d)是t1，将它们进行计算存在t2，有q(* b t1 t2)。
		
		对于q(+ res(a) res(b*(c-d)) t),res(a)是a，res(b*(c-d))是t2，把结果放在t3，有q(+ a t2 t3)。
		
		按最终结果的生成顺序，可得：
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
				\large{	(1)  (-\quad c \quad d\quad t1)\\
					(2)  (*\quad b \quad t1\quad t2)\\
					(3)  (+\quad a \quad t2\quad t3)}
			\end{tcolorbox}
		\end{center}
	\end{example}
	
	\begin{example}
		表达式逆波兰式和四元式最简翻译算法示例：
	\end{example}
	
	(a+b/d)$<$e*(f-g)，pos()?，Quat？
	
	逆波兰式生成要点：运算对象顺序不变，运算符紧跟运算对象之后！
	则：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Polish-example}
		\label{fig:85}
	\end{figure}
	四元式生成要点：按照运算法则，依次生成四元式！
	则：\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
			\large{	(1)  (/\quad b \quad d\quad t1)\\
				(2)  (+\quad a \quad t1\quad t2)\\
				(3)  (-\quad f \quad g\quad t3)\\
				(4)  (*\quad e \quad t3\quad t4)\\
				(5)  (<\quad t2 \quad t4\quad t5)\\
			}
		\end{tcolorbox}
	\end{center}
	四元式实际上和逆波兰式对应，先算b/d，结果和a相加，然后算(f-g)，结果和e相乘，最终把这两个结果t2和t4用<比较，比较的结果存到t5。
	
	2、赋值语句的四元式设计
	
	设有赋值语句：v=E
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-design-1}
		\label{fig:87}
	\end{figure}
	先算表达式右侧的E，再进行赋值。

	\begin{example}
		x=a*(b-c)/(d+e)
	\end{example}

	按照上面的规则，先求quat(E)，把结果赋值给v。Quat(E)按计算的顺序写下来，最后用t4代替res(E)。结果如下图所示：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-design-2}
		\label{fig:88}
	\end{figure}
	
	3、转向语句与语句标号的四元式设计
	
	语句标号为转向语句提供转入语句标识，二者用标号相关联。
	
	（1）设有转向语句：goto i
	
	则有 goto i$\implies$ q( gt  \_  \_  i )
	
	其中gt表示goto
	
	（2）设有标号语句：i：S
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Marking-Statements}
		
		\label{fig:89}
	\end{figure}
	其中，i表示标号，lb表示label，S是后面的语句。
	
	\begin{example}
		goto i；...  i：x=(a+b)/c；
	\end{example}
	
	则有四元式序列
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-sequences}
		
		\label{fig:90}
	\end{figure}
	4、条件语句的四元式设计
	
	（1）文法：\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Grammar}
		
		\label{fig:91}
	\end{figure}
	（2）语义结构：
	从入口进，判断E，为真则执行S1，为假则执行S2，S2路径是可选的，最终都到达出口。
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Semantic-Flowchart}
		
		\label{fig:92}
	\end{figure}
	（3）四元式结构：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-structure}
		
		\label{fig:93}
	\end{figure}
	【注】
	
	q1：当res(E)=False，则转向S2入口四元式；
	
	q2：无条件转向出口四元式；
	
	q3：条件语句出口四元式。
	
	首先执行的是quat(E)，计算表达式E的结果，存到res(E)。 \begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-quat}
		
		\label{fig:94}
	\end{figure}
	表示判断res(E)是否为假，若为假就跳转到quat(S2)，若为真就顺序执行，执行quat(S1)，执行完后跳转到出口。
	\begin{example}
		条件语句四元式翻译示例：
	\end{example}

	
	
	if (a<b) x=a+b；
	
	else y=a-b；
	
	四元式序列：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-sequences-1}
		
		\label{fig:95}
	\end{figure}
	【注】如果语句中没有else y=a-b 部分，则四元式结构中和四元式序列中的相应部分也不存在了！
	
	5、循环语句的四元式设计：
	
	（1）文法：S $\rightarrow$ while (E) S
	
	（2）语义结构：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-design-3}
		
		\label{fig:96}
	\end{figure}
	逻辑是：while语句先判断E，若E为真就执行S，再判断E，还为真则继续执行S，直到E为假则跳到出口。
	
	（3）四元式结构：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-structure-1}
		
		\label{fig:97}
	\end{figure}
	一开始定义q1 ，它是一个标识，表示while的入口。接下来计算quat(E)，然后判断res(E)是否为假，为假则跳出循环，为真则执行S，再通过语句q3 返回计算quat(E)。
	
	【注】
	
	q1：while语句的入口四元式（提供转向E参照）；
	
	q2：当res(E)=False转向出口四元式；
	
	q3：while尾（兼循环转向E）四元式。
	\begin{example}
		循环语句四元式翻译示例：
	\end{example}
	
	
	
	while (a$<$b$\land$$>$c)
	
	\{x=(b+c)/2; a=a-1; \}
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-Quadratic-sequences-2}
		\label{fig:98}
	\end{figure}
	
	表达式a$<$b$\land$a$>$c 用四元式(2)(3)(4)来表示，结果存到t3。S用四元式(6)(7)(8)(9)(10)表示，(6)(7)(8)对应x=(b+c)/2，(9)(10)对应a=a-1。最后是q3，起到跳转的作用，跳转到四元式(2)。
	
	\begin{example}
		逆波兰式（四元式）计算过程示例：
	\end{example}
	
	
	【算法】设置一个“栈”，每当NEXT(w)，重复执行：
	
	（1）若w=运算对象，则压入栈中暂存：PUSH(w)；
	
	（2）若w=运算符，则弹出栈顶对象计算之，并把结果压栈。
	\begin{figure}[H]
		\centering
		%\input{./chapter7/figures/figure-7-27}
		\includegraphics[scale=0.8]{./chapter7/figures/figure-Inverse-Polish-example.eps}
		
		\label{fig:99}
	\end{figure}
	a+b*(c/d-e)的逆波兰式是abcd/e-*+，自左向右扫描，看到第一个运算符/，就把c和d进行运算，对应t1，写成四元式t1=c/d 。继续往后扫描，看到第二个运算符 - ，就把栈顶的两个元素e和t1做减法，结果存在t2。以此类推，可以得到t3、t4。
	
	\section{中间代码翻译算法}
	\subsection{属性文法}
	\begin{definition}
		属性文法是上下文无关文法在语义上的扩展，可定义为如下三元组：
		
		A=( G, V, E )；其中，G（文法），V（属性集），E（属性规则集）。
	\end{definition}
	
	
	说明：
	\begin{enumerate}
		\item 属性：代表与文法符号相关的信息，这里主要指语义信息（类型、种类、值和值地址...）；文法产生式中的每个文法符号都附有若干个这样的属性。比如，描述一个人，身高、头发、颜色、出生地、年龄，都可以称为人的属性。文法符号也可以用若干个属性来描述，比如一个变量，整型/浮点型、值都是属性。
		\item 属性可以进行计算和传递，属性规则就是在同一产生式中，相互关联的属性求值规则。比如，统计一个班级的总分，就是把所有同学的分数相加，如果把分数看成每一个人的属性，把所有分数相加就相当于对属性进行计算。
		\item 属性分两类（按属性求值规则区分）：
		综合属性：其值由子女属性值来计算（自底向上求值）；
		继承属性：其值由父兄属性值来计算（自顶向下求值）。
		比如，对于继承属性，一般而言，姓氏是从父亲那“继承”的，该属性由父亲的属性决定。对于综合属性，父亲的属性需要用孩子的属性计算，以之前班级的例子为例，班级是学生一个更高层次的抽象，对于班级的成绩属性，需要把所有学生的成绩相加求平均来求。
	\end{enumerate}

	
	
	
	\begin{example}	属性文法构造示例：
		
		算数表达式的属性文法；
		
		设：X.val为文法符号X的属性值；
		
		下述属性文法用于算术表达式的求值运算：
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth]	
				\begin{align*}
					&E\ \rightarrow\ E^1\ +\ T\ ;&||&\ E.val:=E^1.val\ +\ T.val\\
					&E\ \rightarrow\ E^1\ -\ T\ ;&||&\ E.val:=E^1.val\ -\ T.val\\
					&E\ \rightarrow\ T\ ;&||&\ E.val:=\ T.val\\
					&T\ \rightarrow\ T^1\ *\ F\ ;&||&\ T.val:=\ T^1.val\ *\ F.val\\
					&T\ \rightarrow\ T^1\ /\ F\ ;&||&\ T.val:=\ T^1.val\ /\ F.val\\
					&T\ \rightarrow\ F\ ;&||&\ T.val:=\ F.val\\
					&F\ \rightarrow(E);&||&\ F.val:=\ E.val\\
					&F\ \rightarrow i;&||&\ F.val:=\ i.val
				\end{align*}
			\end{tcolorbox}
		\end{center}
		
		表的左侧是原始的文法，右侧是属性文法。对于$E\rightarrow E^1 + T$ ，
		$E^1$与$E$是不同的，其它加了上标1的符号同理。它对应的属性文法是右侧 ，将$E^1$的值加上T的值的结果赋给$E$。-、*、/都类似。可以看出，该X.val属性是综合属性。
		对于表达式 ，$E$相当于树的根，$E^1$、T相当于树的叶子，父亲的属性值是由孩子的属性值决定的。
		
		属性计算过程示例：
		
		根据算术表达式属性文法及其相应的属性求值规则，2+4*(5-9/3)的属性语法树：
		\begin{figure}[H]
			\centering
			\includegraphics[scale=0.6]{./chapter7/figures/figure-Property-Syntax-Tree.eps}
			\label{fig:101}
		\end{figure}
		
		如何算这个属性？基于最左推导或最左归约，传递规则是从下往上，比如2传给F，F传给T，T传给$E^1$，然后还有相对复杂的计算，最后得到最上面的$E$，也就是整个表达式对应的文法符号的值为10。这个过程和之前描述的属性文法是一致的，父亲的属性值需要通过孩子进行计算，也就是说，如果得到了属性的值，就可以得到整个表达式的计算结果。
	\end{example}
	
	
	
	\subsection{语法制导翻译技术}
	\begin{definition} 语法制导（syntax\_directed）\\
		是指根据语言的形式文法对输入序列进行分析、翻译处理；核心技术是构造翻译文法——在源文法产生式中插入语义动作符号（翻译子程序），借以指明属性文法中的属性求值时机和顺序。
	\end{definition}
	
	
	语法制导翻译指在语法分析过程中，通过加入语义动作，来完成中间代码的生成，生成的过程称为翻译。语法制导强调所有定义、计算、建模，全都是基于语法的，在本编译原理教程中，语法是核心，决定程序的结构或系统的架构，把词法和中间代码生成连接起来。
	
	翻译文法可以看成是一种属性文法，带有属性的计算。语法制导的翻译，没有一个独立的程序来得到中间代码，中间代码的生成是贯穿在语法分析过程中的，语法分析执行完了，中间代码也就生成出来了。
	语法制导翻译技术由两部分构成：
	\begin{center}
		语法分析技术 + 翻译文法构造技术
	\end{center}
	为叙述简便，除非临时详细指明，标识符X的属性一律视为符号表项指针，同时用X表示X.point。接下来的大部分例子，将以算术表达式文法为例，探讨翻译文法的构造。
	
	逆波兰式翻译文法构造示例：
	
	\begin{example} 算术表达式逆波兰式翻译文法\\
		\begin{figure}[H]
			\centering
			\input{./chapter7/figures/figure-Inverse-Polish-Translation-Grammar}
			
			\label{fig:102}
		\end{figure}
		
		该文法和简单的算术表达式稍有区别，大括号{}里面的是语义动作，去掉{}及里面的内容，剩下的内容就是标准的算术表达式文法。{a}的含义是输出(a)。
		
		符号串a*(b+c)的分析（翻译）过程（推导法）：
		\begin{figure}[H]
			\centering
			\input{./chapter7/figures/figure-103-analysis-process-31}
			
			\label{fig:103}
		\end{figure}
		用推导的方式，首先，E用T来推导，先推导*乘法。然后是T*F{*}，比原始文法多了{*}，但还是按照文法内容完整推导出来。接下来用$T\rightarrow F$把T推导成F，得$F*F\{*\}$。再将第一个F推导成$a\{a\}$ ，第二个F推导成$(E)$ ，E就是b+c。$(E)$ 再推导成$(E+T\{+\})$ ，需要带上{+}。接下来的步骤类似。
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
				\begin{align*}
					\text{分解导出序列}&:&\\
					\text{去掉动作符号}&:&a*(b+c) ......\text{源表达式};\\
					\text{去掉文法符号}&:&abc+*......\text{逆波兰式};
				\end{align*}
			\end{tcolorbox}
		\end{center}
	
		大括号$\{\}$是定义的一种动作，可以看作程序执行的一段代码，并不是文法真实的符号，代表的是程序要执行的一个操作。通过在语法中加入语义动作，在使用推导的方法进行语法分析后，就能得到一个动作序列，结果就是输出逆波兰式，达到生成中间代码的目的。
	\end{example}
	

	
	这个例子说明，通过改造文法，不需要额外地设计新的复杂程序，就能生成逆波兰式。
	
	四元式翻译文法构造示例1：
	
	1、从逆波兰式的翻译到四元式的翻译：
	
	假定：\{a\}为PUSH(a)，即把a压入栈（语义栈）中。
	
	则算术表达式a+b*(c/d-e)的逆波兰式（生成）计算顺序：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-137-reverse-polish-calculation-process-33}
		\label{fig:137}
	\end{figure}
	往栈里依次压入元素a、b、c、d，当遇到 / 时，就用栈顶的两个符号和 / 一起生成四元式t1=c/d。同样，当遇到第二个运算符 - 时，就用栈顶符号t1和e生成第二个四元式。四元式（3）（4）同理。
	
	\{a\}代表了压栈操作，当遇到运算符，就用栈顶符号生成四元式，并把结果变量压回栈里。
	
	四元式翻译文法构造示例2：
	
	2、算术表达式四元式翻译文法设计
	
	定义：
	
	SEM(m)——语义栈（属性传递、赋值场所），可以理解为一个指向符号表的指针，记录了所有关于这个标识符的信息；
	
	QT[q]——四元式区，存储生成的四元式；
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法定义$G''(E)$,valign=scale,halign=center,width=10cm]
			\begin{align*}
				&E\rightarrow T\ |\ E+T\{GEQ(+)\}\ |\ E-T\{GEQ(-)\}\\
				&T\rightarrow F\ |\ T*F\{GEQ(*)\}\ |\ T/F\{GEQ(/)\}\\
				&F\rightarrow\ i\{PUSH(i)\}\ |\ (E)
			\end{align*}
		\end{tcolorbox}
	\end{center}
	其中：
	
	（1）PUSH(i)——压栈函数（把当前i压入语义栈）；
	
	（2）GEQ($\omega$)——表达式四元式生成函数：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-139-quaternion-generating-function-35}
		\label{fig:139}
	\end{figure}
	有三个步骤：一，申请变量t，；二，生成四元式，用ω进行计算，操作数是栈顶的两个元素，SEM[m-1]是次栈顶元素，SEM[m]是栈顶元素，把结果存在t；三，分别是弹栈、弹栈、压栈，即把栈顶的两个元素出栈，再把结果压入栈。
	
	动作函数（序列）执行过程示例：
	
	算术表达式a*(b/c-d)的逆波兰式abc/d-*，可得四元式动作序列：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-140-quaternary-action-sequence-36}
		\label{fig:140}
	\end{figure}
	PUSH(a)、PUSH(b)、PUSH(c)分别压栈，GEQ(/)用栈顶两个元素b和c生成四元式，弹出b和c并把结果t1压栈。之后同理，最终得到结果t3。
	\subsection{四元式翻译文法设计扩展1}
	1、赋值语句四元式翻译文法：
	
	S $\rightarrow$ v{PUSH(v)} = E{ASSI(=)}；
	
	赋值语句的表达式v=E，它的翻译文法步骤是通过加入两个语义动作{PUSH(v)}和{ASSI(=)}，其中，ASSI(=)——赋值函数，把栈顶元素赋值给次栈顶元素，然后把栈顶和次栈顶元素弹出，如下图。
	\begin{center}
			\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
			\begin{align*}
				&(1)SEND(:=\ SEM[m],\_,SEM[m-1]);\\
				&(2)POP;POP;
			\end{align*}
		\end{tcolorbox}
	\end{center}

	2、标号、转向语句四元式翻译文法：
	
	S $\rightarrow$ i {PUSH (i)} : {LABEL(i)} S；
	
	S $\rightarrow$ goto i {GOTO(i)} ；
	
	其中，LABEL(i)——标号函数，跳转到语义栈栈顶的元素所对应的那行代码，然后将栈顶元素弹出，如(1)SEND(lb\  \_\_\ ,\_\_\ ,\ SEM[m]);(2)pop; ，SEM[m]是i；
	GOTO(i)——转向函数，跳转到i，如(1)SEND(gt\  \_\_\ ,\_\_\ ,\ i);
	
	3、条件语句四元式翻译文法：
	
	S $\rightarrow$ if(R) \{IF(if)\} S; [else \{EL(el)\}S] \{IE(ie)\} 
	IF(if)——if 函数，用if来判断栈顶符号是否为假，SEM[m]存的是R的结果；如图
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,valign=scale,halign=center,width=\columnwidth/2]	
			\begin{align*}
				&(1)SEND(if\ SEM[m],\_,\_);\\
				&(2)POP;
			\end{align*}
		\end{tcolorbox}
	\end{center}

EL(el)——else函数，跳出if；如图
	\begin{center}
	\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
		$(1)SEND(el\ \_,\_,\_);$
		\end{tcolorbox}
	\end{center}

IE(i)——ifend函数，指示if的结束；如图
\begin{center}
\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
		$(1)SEND(ie\ \_,\_,\_);
	$
	\end{tcolorbox}
\end{center}

	循环语句四元式翻译文法：
	
	S $\rightarrow$ while {Wh()} (R) {DO(do)} S {WE(we)}；
	
	WH(wh)——循环头函数，标识while的开始；如图
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			$(1)SEND(wh\ \_,\_,\_);$
		\end{tcolorbox}
	\end{center}

	DO(el)——DO函数，条件判断，判断SEM[m]栈顶元素的值是否为假，若为假则跳到函数尾，不为假则继续执行；如图
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,width=\columnwidth/2,notitle]	
			\begin{align*}
				&(1)SEND(do\ SEM[m],\_,\_);\\
				&(2)POP;
			\end{align*}
		\end{tcolorbox}
	\end{center}

WE(we)——循环尾函数，表示条件的结束，还要再一次判断R的值是否为假，跳回到while的入口；如图
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			
				$(1)SEND(we\ \_,\_,\_);$
			
		\end{tcolorbox}
	\end{center}

【注】文法中的R为关系表达式（见条件语句四元式翻译文法）

4、说明语句四元式翻译文法：

（1）
\begin{center}
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=原文法：,valign=scale,halign=center,width=10cm]
		\begin{align*}
			&D\rightarrow id:T;D\ |\ id:T\ \\
			&T\rightarrow interger\ |\ real\ |\ array[num]\ of\ T\ |\ \uparrow T\\ 
		\end{align*}
	\end{tcolorbox}
\end{center}
对该文法进行改造。

（2）

\begin{center}
	\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=文法转换：,valign=scale,halign=center,width=10cm]
		\begin{align*}
			&D\rightarrow id:T;D'\\
			&D'\rightarrow ;id:TD'\ |\ \varepsilon \\ 
			&T\rightarrow interger\ |\ real\ |\ array[num]\ of\ T\ |\ \uparrow T\\
		\end{align*}
	\end{tcolorbox}
\end{center}

	（3）
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=翻译文法：,valign=scale,halign=center,width=10cm]
			\begin{align*}
				&D\rightarrow \{INI()\}id\{NAME()\}:T\{ENT()\}D'\\
				&D'\rightarrow ;id\{NAME()\}:T\{ENT()\}D'\ |\ \varepsilon \\ 
				&T\rightarrow interger\{TYP(i)\}\ |\\ &\rightarrow real\{TYP(r)\}\ |\\
				&\rightarrow array[num]\ of\ T\{TYP(a)\}\ |\\
				&\rightarrow \uparrow T\{TYP(\uparrow T)\}
			\end{align*}
		\end{tcolorbox}
	\end{center}

	INI()——初始化函数，在文法的开始，只能有一次。D的产生式完成的是初始化的操作，而D’不需要，这也是文法变换的一个目的，把第一个变换提取出来。
	
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			$(1)offset:=0;$
		\end{tcolorbox}
	\end{center}

NAME()——标识符，名字处理函数，得到标识符对应的地址，存在该属性值；
		\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			$(1)id.name:=entry(id);$
		\end{tcolorbox}
	\end{center}

ENT()——填写符号表函数，根据名字、类型、偏移，把变量存入活动记录相应位置，同时offset要加上变量的长度；
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			$(1)enter(id.name,T.type,offset);$\\
			$(2)offset:=offset+T.width;$
		\end{tcolorbox}
	\end{center}

TYP(x)——标识符类型处理函数，用x表示T的类型，x的width表示T的width；
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			$T.type:=x;\quad T.width:=x.width;$
		\end{tcolorbox}
	\end{center}

NUM()——标识符类型处理函数，将变量的值存到对应的val属性；
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			$num.val:=val(num);$
		\end{tcolorbox}
	\end{center}
	
	
	翻译文法应用验证示例
	\begin{example}
		已知条件语句 if(a<0) a=a+1;
	\end{example}

	
	（1）通过语法制导分析（属性推导树），写出动作序列：
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-119-action-sequence-52}
		 
		\label{fig:119}
	\end{figure}
	所以if(a<0) a=a+1四元式翻译的动作序列依次是：
	{push(a)}，{push(b)}，{GEQ(<)}，{IF(if)}，{PUSH(a)}，{push(a)}，{push(1)}，{GEQ(+)}，{ASSI(=)}，{IE(ie)}
	
	（2）根据上述条件语句四元式翻译的动作序列，if(a<0) a=a+1的四元式生成过程：
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-120-quaternion-generation-process-53}
		 
		\label{fig:120}
	\end{figure}
	
	\section{中间代码翻译的实现}
	语法制导翻译的结构，可描述为：
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=darkgray,boxrule=0.1em,halign=center,width=\columnwidth/2,notitle]	
			扩展的\textbf{语法分析器}\ \textcircled{+}\ \textbf{翻译文法}
		\end{tcolorbox}
	\end{center}
	语法分析器用文法对序列进行分析。翻译文法的设计，即在文法中加入语义动作，执行语法分析的过程同时执行翻译的过程。
	
	1、自顶向下的翻译文法的要求：
	
	（1）源文法应满足自顶向下分析要求（如LL(1)文法）；
	
	（2）属性是自顶向下可求值的（属性计算不发生冲突）；
	
	（3）动作符号可插入到产生式右部任何位置。
	
	2、自底向上翻译文法的要求：
	
	（1）源文法应满足自底向上分析要求（如LR()文法）；
	
	（2）属性是自底向上可求值的（属性计算不发生冲突）；
	
	（3）动作符号只能位于产生式的最右端。
	\subsection{ 递归子程序翻译法}
	\begin{example}
	算术表达式四元式翻译器的设计1：
	\label{ex:7-14}
	\end{example}

	
	1、设置
	
	语义栈：SEM[m]——暂存运算对象的属性值。
	
	四元式区：QT[q]——四元式生成结果的存储区。
	
	
	2、翻译文法设计
	
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G1(E)：,valign=scale,halign=center,width=10cm]
			\begin{align*}
				&E\rightarrow T\{+T\{GEQ(+)\}\ |\ -T\{GEQ(-)\}\}\\
				&T\rightarrow F\{*F\{GEQ(*)\}\ |\ /T\{GEQ(/)\}\}\\
				&F\rightarrow i\{PUSH(i)\}\ |\ (E)\\
			\end{align*}
		\end{tcolorbox}
	\end{center}


	3、递归子程序的扩展
	
	用递归子程序来分析文法，求四元式序列。要求：
	
	\ding{172}动作符号在哪，就在哪执行之；
	
	\ding{173}主控程序(Z  $\rightarrow$ E)功能：初始化；结果输出。
	
	算术表达式翻译文法的递归子程序：
	
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-123-recursive-subroutine1-56}
		 
		\label{fig:123}
	\end{figure}
	
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-124-recursive-subroutine2-57}
		 
		\label{fig:124}
	\end{figure}
	算术表达式四元式翻译过程：
	
	递归子程序调用算法为：入口时，把返回地址压入返回地址栈并进入；出口时，把返回地址弹出返回地址栈并返回。
	
	设待翻译的表达式为a*(b/c)\#，执行递归子程序的过程如下：
	
	首先，压入Z，然后读取w=a，调用子程序E，进入返回地址R0。在子程序E中，先压入T，而在子程序中，又读入F，返回R4。在子程序F，先判断是不是i，是i则执行PUSH(i)，把i压入到语义栈，然后再读取w，跳出子程序F，回到R4。接下来的过程不再赘述，最终分析结束的时候，会生成两个四元式，如表所示。
	
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-125-execute-recursive-subroutine-58}
		 
		\label{fig:125}
	\end{figure}
	\subsection{LL(1)翻译法}
	\begin{example}
		算术表达式四元式翻译器的设计2：
		\begin{enumerate}
			\item 设置
			语法栈：SYN[n]；
			
			语义栈：SEM[m]；
			
			四元式区：QT[q]；
			\item 翻译文法设计
			将例\ref{ex:7-14}的文法改造成右递归的形式
			\begin{center}
				\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=右递归改造文法,valign=scale,halign=center,width=15cm]
					$E\rightarrow TE'\ (1)$\\
					$E'\rightarrow +T \{GEQ(+)\}\ E'\ (2)\ |-T \{GEQ(-)\}\ E'\ (3)\ |\ \varepsilon\ (4) $\\
					$T\rightarrow FT'\ (5) $\\
					$T'\rightarrow *F\{GEQ(*)\}T'(6) \ |\ /F\{GEQ(/)\}T'(7) |\ \varepsilon\ (8)$\\
					$F\rightarrow i\{PUSH(i)\}\ (9) \ |\ (E)\ (10)$\\
				\end{tcolorbox}
			\end{center}
		\end{enumerate}
	\end{example}

	

	
	

	
	
	
	
	3、LL(1)分析器的扩展
	
	（1）当产生式（逆序）压栈是，动作符号也不例外；
	
	（2）当动作符号位于栈顶时，执行之。
	
	
	算术表达式四元式翻译过程：
	
	首先得到LL(1)分析表：
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}[>=latex,every node/.style={,inner sep=0}]
			
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			\node[drop shadow, fill=white] at (5em,0) (SYNBL){
				\begin{tabular}{|C{2em}|C{2em}|C{2em}|C{2em}|C{2em}|C{2em}|C{2em}|C{2em}|C{2em}|} \hline
					\diagbox{}{} & i& + &- &* &/ & ( & ) & \# \\ \hline
					E & \ding{172} & ~ & ~ & ~ &~ & \ding{172} & ~& ~ \\ \hline
					E' & ~ & \ding{173} & \ding{174} & ~ ~ && ~ & \ding{175}& \ding{175} \\ \hline
					T & \ding{176} & ~ & ~ & ~ &~& \ding{176} & ~&  \\ \hline
					T' & ~ & \ding{179} & \ding{179} & \ding{177} & \ding{178} & ~& \ding{179}&\ding{179} \\ \hline
					F & \ding{180} & ~ & ~ & ~ & ~ & \ding{181}& ~&~ \\ \hline
					
				\end{tabular}
			};
		\end{tikzpicture}
		\caption{LL(1)分析表}
		\label{fig:133}
	\end{figure}
	

	设待翻译的表达式为a+b*c\#，分析的过程如下：
	
	栈底是\#和E，x是栈顶符号E，w是当前要处理的符号a。E看到a，是产生式\ding{172}，所以push(E)，把E产生式的右部逆序压栈，把T放到x。T遇到a，把产生式 \ding{176}逆序压栈，此时栈顶符号是F，F遇到a，把产生式 \ding{180}逆序压栈。压栈时，把PUSH(i)当成一个元素，即把PUSH(a)、a依次压栈。栈顶是a，w也是a，做匹配操作，读取下一个符号+。栈顶符号是PUSH(a)，执行该语义动作，把a压入语义栈SEM[m]，SYN[n]的栈顶元素变为T`。把T`存到x，T`遇到+，把产生式 \ding{179}逆序压栈，产生式 \ding{179}是空，所以不用压栈。接着是E`遇到+，产生式\ding{173}逆序压栈，把栈顶符号+存到x，匹配+。读取下一个符号b，T遇到b，逆序压栈产生式 \ding{176}。接下来的过程不再赘述，最终\#和\#匹配，生成两个四元式，如下表。
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-128-ll1-analysis-process-61}
		 
		\label{fig:128}
	\end{figure}
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-129-ll1-analysis-process-62}
		 
		\label{fig:129}
	\end{figure}
	这个过程和语法分析是类似的，不同的是加入了一些语义动作，当栈顶是语义动作时，就执行相应的动作。
	\subsection{LR()翻译法}
	\begin{example}
		算术表达式四元式翻译器的设计3：
	\end{example}
	
	1、设置
	
	语法栈：SYN[n]；
	
	语义栈：SEM[m]；
	
	四元式区：QT[q]；
	
	2、
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=翻译文法设计（带有状态编码）,valign=scale,halign=center,width=10cm]
			$Z\rightarrow E_1\ (0)$\\
			$E\rightarrow E_2 +_3 T_4 \{GEQ(+)\}\ (1)\ | T_5\ (2) $\\
			$T\rightarrow T_6 *_7 F_8\{GEQ(*)\}\ (3) |\ F_9\ (4) $\\
			$F\rightarrow i_{10} \{PUSH(i)\}\  (5)\ |\ (_{11}\ E_{12}\ )_{13}\ (6) $\\
		\end{tcolorbox}
	\end{center}
	注意，自底向上翻译文法的语义动作只能在产生式的最右端。
	
	3、LR()分析表的扩展
	
	LR()分析表中的r(i)执行下述两种操作：
	
	\ding{172}首先执行动作符号（翻译函数）；
	
	\ding{173}然后执行归约操作（按产生式i归约）。
	
	SLR(1)分析表的构造：
	\begin{figure}[H]
		\centering
		\begin{tikzpicture}[>=latex,every node/.style={,inner sep=0}]
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			\node[drop shadow, fill=white] at (5em,0) (SYNBL){
				\begin{tabular}{|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|} \hline
					\diagbox{}{} & i& + & *  & ( & ) & \# & E & T & F\\ \hline
					0 & i10 & ~ & ~ & (11) & ~ & ~& E1,2& T5,6&F9\\ \hline
					1,2 & ~ & +3 & ~ & ~ & ~ & OK& ~& ~& ~\\ \hline
					3 & i10 & ~ & ~ & (11) & ~ & ~& ~& T4,6& F9\\ \hline
					4,6 & ~& r(1) & *7& ~ & r(1) & r(1) & ~& ~& ~\\ \hline
					5,6 & ~ & r(2) & *7 & ~ & r(2) & r(2) & ~& ~& ~\\ \hline
					7 & i10 & ~ & ~ & (11) & ~ & ~& ~& ~& F8\\ \hline
					8 &r(3) & r(3) & r(3) &r(3) & r(3) & ~ & ~& ~ & ~\\ \hline
					9&r(4) & r(4) & r(4) &r(4) & r(4) & ~ & ~& ~ & ~\\ \hline
					10 &r(5) & r(5) & r(5) &r(5) & r(5) & ~ & ~& ~ & ~\\ \hline
					11 & i10 & ~ & ~ & (11 & ~ & ~& E1,2& T5,6&F9\\ \hline
					12,2 &~ & +3 & ~ &~ & )13 & ~ & ~& ~ & ~\\ \hline
					13 &r(6) & r(6) & r(6) &r(6) & r(6) & ~ & ~& ~ & ~\\ \hline
				\end{tabular}
			};
		\end{tikzpicture}
		\label{fig:131}
	\end{figure}
	算术表达式四元式翻译过程：
	设待翻译的表达式为a*b+c\#，分析过程如下：
	首先把0状态压栈，0状态看到a到10状态，压入a10。10状态看到\#，执行r(5)，归约产生式（5）。归约的时候，先执行PUSH(a)，把a压入语义栈，再归约a，压入F9。9状态看到*，归约产生式（4），归约成T。0状态看到T，是T5,6状态，5,6状态是一起的，是确定化之后得到的。T5,6状态看到*到7状态，随后的过程与前面类似，这里不再赘述，最终得到整个分析过程。
	
	
	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-132-arithmetic-expression-translation-process-65}
		 
		\label{fig:132}
	\end{figure}
	\subsection{算符优先翻译法}
	\begin{example}
		算术表达式四元式翻译器的设计4：
	\end{example}

	
	1、设置
	
	语法栈：SYN[n]；
	
	语义栈：SEM[m]；
	
	四元式区：QT[q]；
	
	2、翻译文法设计
	
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=翻译文法：,valign=scale,halign=center,width=10cm]
			$E\rightarrow E + T\{GEQ(+)\}\ | T $\\
			$T\rightarrow T * F\{GEQ(*)\}\ | F $\\
			$F\rightarrow i\{PUSH(i)\}\ | E $\\
		\end{tcolorbox}
	\end{center}

1、算符优先分析器的扩展

（1）归约时，先执行语义动作，后归约；

（2）归约时，只要产生式右部的终结符排列和栈顶$<$·......·$>$中的终结符匹配上即可；

（3）归约后，得到的非终结符不必入栈。

（4）	算术表达式四元式翻译过程：

	\begin{figure}[H]
		\centering
	\begin{tikzpicture}[>=latex,every node/.style={,inner sep=0}]
		
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		\node[drop shadow, fill=white] at (5em,0) (SYNBL){
			\begin{tabular}{|C{2em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|C{3em}|} \hline
				\diagbox{}{} & + & * & i & ( & ) & \#\\ \hline
				+ & > & < & < & < & > & >\\ \hline
				* & > & > & < & < & > & >\\ \hline
				i & >& > & ~& ~ & > & > \\ \hline
				( & < & < & < & < & = & > \\ \hline
				) & > & > & ~ & ~ & > & > \\ \hline
				\# &< & < & < &< & < & OK  \\ \hline
			\end{tabular}
		};
	\end{tikzpicture}
		\caption{优先级图}
		\label{fig:134}
	\end{figure}
设待翻译的表达式为a+b*c\#，分析过程为：	
首先压入\#，如果关系是<，就移进，如果是>就归约，用 归约，先执行PUSH(a)，再归约成F。剩下过程不再赘述，只需注意归约时要加上语义动作。

	\begin{figure}[H]
		\centering
		\input{./chapter7/figures/figure-135-operator-precedence-parser-68}
		 
		\label{fig:135}
	\end{figure}
	\subsection{翻译文法的变换问题}
	自底向上中间代码翻译，要求翻译文法的动作符号必须位于产生式的最右端。不满足此条件的属性翻译文法，需要通过文法变换来解决。
	\begin{enumerate}
		\item 赋值语句的属性翻译文法：
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(S)：,valign=scale,halign=center,width=15cm]
				S  $\rightarrow$ v{PUSh(v)} = E{ASSI(=)}；
			\end{tcolorbox}
		\end{center}
		改造文法，令Sa  $\rightarrow$ v{PUSh(v)}，
		
		则有：
		
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G`(S)：,valign=scale,halign=center,width=15cm]
				S  $\rightarrow$ Sa = E{ASSI(=)}；\\
				S  $\rightarrow$ v{PUSh(v)}；
			\end{tcolorbox}
		\end{center}
		\item 标号、转向语句属性翻译文法：
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(S)：,valign=scale,halign=center,width=15cm]
					S  $\rightarrow$ i {PUSH(i)} : {LABEL(i)} S；
				
				S  $\rightarrow$ goto i {GOTO(i)}；
			\end{tcolorbox}
		\end{center}
		令 Si  $\rightarrow$ i {PUSH(i)}\\
		
		SI  $\rightarrow$ Si : {LABEL(i)} 
		则有：
		\begin{center}
			\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G`(S)：,valign=scale,halign=center,width=15cm]
				S  $\rightarrow$ SI S；\\
				SI  $\rightarrow$ Si : {LABEL(i)}\\
				Si  $\rightarrow$ i {PUSH(i)}
			\end{tcolorbox}
		\end{center}
	
	\item 分支语句的翻译文法
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(S)：,valign=scale,halign=center,width=15cm]
			S  $\rightarrow$ if(R) {IF(if)}S；
			
			[else {El(el)}S] {IE(ie)}
		\end{tcolorbox}
	\end{center}
	令 Sif  $\rightarrow$ if(R) {IF(if)}
	
	则有：
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G'(S)：,valign=scale,halign=center,width=15cm]
			S  $\rightarrow$ Sif S；[Sel S] {IE(ie)}
			
			S  $\rightarrow$ if(R) {IF(if)}
		\end{tcolorbox}
	\end{center}

	\item 循环语句的翻译文法
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G(S)：,valign=scale,halign=center,width=15cm]
			S  $\rightarrow$ while{WH()} (R) {DO(do)} S {WE(we)}
		\end{tcolorbox}
	\end{center}
	令 Swh  $\rightarrow$ while{WH()}
	Sdo  $\rightarrow$ (R) {DO(do)}

	则有：
	\begin{center}
		\begin{tcolorbox}[colback=white,colframe=blue!75!black,title=G'(S)：,valign=scale,halign=center,width=15cm]
				S  $\rightarrow$ Swh Sdo S{WE(we)}
			
			Swh  $\rightarrow$ while{WH()}
		\end{tcolorbox}
	\end{center}
	\end{enumerate}

	
	
	

	

	
	
